/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/remove-arbitrary
   @Language: C++
   @Datetime: 20-01-16 14:26
   */

// Method 1, stringstream, 123ms
class Solution {
public:
	/**
	 * @param s: the original string
	 * @return: the string without arbitrary spaces
	 */
	string removeExtra(string &s) {
		// write your code here
		string str;
		for(stringstream istr(s); istr>>s; str+=s+" ");
		if (str.length()) str.pop_back();
		return str;
	}
};

// Method 2, inplace, 164ms
class Solution {
public:
	/**
	 * @param s: the original string
	 * @return: the string without arbitrary spaces
	 */
	string removeExtra(string &s) {
		// write your code here
		int size=0, need=0;
		for(int i=0; i<s.length(); ++i){
			if (s[i]!=' '){
				s[size++]=s[i];
				need=1;
			}
			else if (need){
				s[size++]=' ';
				need=0;
			}
		}
		if (s.length()>=size && s[size-1]==' ') --size;
		return s.substr(0, size);
	}
};
